{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Achievable Transfer Requests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #backtracking #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #回溯 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumRequests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最多可达成的换楼请求数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们有&nbsp;<code>n</code>&nbsp;栋楼，编号从&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;。每栋楼有若干员工。由于现在是换楼的季节，部分员工想要换一栋楼居住。</p>\n",
    "\n",
    "<p>给你一个数组 <code>requests</code>&nbsp;，其中&nbsp;<code>requests[i] = [from<sub>i</sub>, to<sub>i</sub>]</code>&nbsp;，表示一个员工请求从编号为&nbsp;<code>from<sub>i</sub></code>&nbsp;的楼搬到编号为&nbsp;<code>to<sub>i</sub></code><sub>&nbsp;</sub>的楼。</p>\n",
    "\n",
    "<p>一开始&nbsp;<strong>所有楼都是满的</strong>，所以从请求列表中选出的若干个请求是可行的需要满足 <strong>每栋楼员工净变化为 0&nbsp;</strong>。意思是每栋楼 <strong>离开</strong>&nbsp;的员工数目 <strong>等于</strong>&nbsp;该楼 <strong>搬入</strong>&nbsp;的员工数数目。比方说&nbsp;<code>n = 3</code>&nbsp;且两个员工要离开楼&nbsp;<code>0</code>&nbsp;，一个员工要离开楼&nbsp;<code>1</code>&nbsp;，一个员工要离开楼 <code>2</code>&nbsp;，如果该请求列表可行，应该要有两个员工搬入楼&nbsp;<code>0</code>&nbsp;，一个员工搬入楼&nbsp;<code>1</code>&nbsp;，一个员工搬入楼&nbsp;<code>2</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你从原请求列表中选出若干个请求，使得它们是一个可行的请求列表，并返回所有可行列表中最大请求数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/09/26/move1.jpg\" style=\"height: 406px; width: 600px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>请求列表如下：\n",
    "从楼 0 离开的员工为 x 和 y ，且他们都想要搬到楼 1 。\n",
    "从楼 1 离开的员工为 a 和 b ，且他们分别想要搬到楼 2 和 0 。\n",
    "从楼 2 离开的员工为 z ，且他想要搬到楼 0 。\n",
    "从楼 3 离开的员工为 c ，且他想要搬到楼 4 。\n",
    "没有员工从楼 4 离开。\n",
    "我们可以让 x 和 b 交换他们的楼，以满足他们的请求。\n",
    "我们可以让 y，a 和 z 三人在三栋楼间交换位置，满足他们的要求。\n",
    "所以最多可以满足 5 个请求。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/09/26/move2.jpg\" style=\"height: 327px; width: 450px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 3, requests = [[0,0],[1,2],[2,1]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>请求列表如下：\n",
    "从楼 0 离开的员工为 x ，且他想要回到原来的楼 0 。\n",
    "从楼 1 离开的员工为 y ，且他想要搬到楼 2 。\n",
    "从楼 2 离开的员工为 z ，且他想要搬到楼 1 。\n",
    "我们可以满足所有的请求。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 20</code></li>\n",
    "\t<li><code>1 &lt;= requests.length &lt;= 16</code></li>\n",
    "\t<li><code>requests[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= from<sub>i</sub>, to<sub>i</sub> &lt; n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-achievable-transfer-requests](https://leetcode.cn/problems/maximum-number-of-achievable-transfer-requests/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-achievable-transfer-requests](https://leetcode.cn/problems/maximum-number-of-achievable-transfer-requests/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]', '3\\n[[0,0],[1,2],[2,1]]', '4\\n[[0,3],[3,1],[1,2],[2,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        for i in range(len(requests), 0, -1):\n",
    "            for comb in combinations(requests, i):\n",
    "                cnts = [0] * n\n",
    "                for a,b in comb:\n",
    "                    cnts[a] +=1\n",
    "                    cnts[b] -=1\n",
    "                if all(c == 0 for c in cnts):\n",
    "                    return i\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        l = len(requests)\n",
    "        ans = []\n",
    "\n",
    "        def dfs(_n, res, flag):\n",
    "            if _n == l:\n",
    "                for i in flag:\n",
    "                    if i != 0:\n",
    "                        return\n",
    "                ans.append(res)\n",
    "                return\n",
    "\n",
    "            for i in range(2):\n",
    "                if i == 0:\n",
    "                    flag[requests[_n][0]] += 1\n",
    "                    flag[requests[_n][1]] -= 1\n",
    "                    dfs(_n+1, res+1, flag)\n",
    "                    flag[requests[_n][0]] -= 1\n",
    "                    flag[requests[_n][1]] += 1\n",
    "                else:\n",
    "                    dfs(_n+1, res, flag)\n",
    "        dfs(0, 0, [0 for i in range(n)])\n",
    "        return max(ans)\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        def test(result):\n",
    "            dict1 = {}\n",
    "            dict2 = {}\n",
    "            for i in result:\n",
    "                dict1[i[0]] = dict1.get(i[0], 0) + 1\n",
    "                dict2[i[1]] = dict2.get(i[1], 0) + 1\n",
    "            return len(dict1) > 0 and len(dict2) > 0 and dict1 == dict2\n",
    "        l = len(requests)\n",
    "        res = []\n",
    "        # 选k个进行不重复组合\n",
    "        def dfs(temp, cur, k):\n",
    "            # 不够选了，剪枝\n",
    "            # print(cur)\n",
    "            # print(temp)\n",
    "            if len(temp) + l - cur < k or cur > l:\n",
    "                return\n",
    "            # 满足条件，加入结果集\n",
    "            if len(temp) == k:\n",
    "                if test(temp) and temp not in res:\n",
    "                    res.append(temp[:])\n",
    "                    return\n",
    "                else:\n",
    "                    return\n",
    "            # 不选择当前请求\n",
    "            dfs(temp, cur + 1, k)\n",
    "            # 选择当前请求\n",
    "            dfs(temp + [requests[cur]], cur + 1, k)\n",
    "                \n",
    "        # dfs([], 0, 3)\n",
    "        # print(res)\n",
    "        for i in range(0, l + 1):\n",
    "            dfs([], 0, i)\n",
    "        if len(res) == 0:\n",
    "            return 0\n",
    "        maxres = len(res[0])\n",
    "        # print(res)\n",
    "        for j in range(len(res)):\n",
    "            maxres = max(maxres, len(res[j]))\n",
    "        return maxres"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        maxNum  = []\n",
    "        reqNum = len(requests)\n",
    "        arr = [0]*n\n",
    "        asertarr = [0]*(n)\n",
    "        path = []\n",
    "        # 从输入看\n",
    "        # 当前操作：第i个要求选还是不选\n",
    "        # 子问题：从>=i中选要求构造子集\n",
    "        # 下一个子问题：从>=i+1中选要求构造子集\n",
    "        def dfs(i:int):\n",
    "            if i == reqNum:\n",
    "                if arr == asertarr:\n",
    "                    length = len(path)\n",
    "                    # if length> maxNum :\n",
    "                    #     maxNum = length\n",
    "                    maxNum.append(length)\n",
    "                return\n",
    "            \n",
    "            #不选\n",
    "            dfs(i+1)\n",
    "            #选\n",
    "            request = requests[i]\n",
    "            path.append(request)\n",
    "            fromLayer= request[0]\n",
    "            toLayer = request[1]\n",
    "            arr[fromLayer] = arr[fromLayer]-1\n",
    "            arr[toLayer] = arr[toLayer]+1\n",
    "            dfs(i+1)\n",
    "            arr[fromLayer] = arr[fromLayer]+1\n",
    "            arr[toLayer] = arr[toLayer]-1\n",
    "            path.pop()\n",
    "        dfs(0)\n",
    "        return max(maxNum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        def test(result):\n",
    "            dict1 = {}\n",
    "            dict2 = {}\n",
    "            for i in result:\n",
    "                dict1[i[0]] = dict1.get(i[0], 0) + 1\n",
    "                dict2[i[1]] = dict2.get(i[1], 0) + 1\n",
    "            return len(dict1) > 0 and len(dict2) > 0 and dict1 == dict2\n",
    "        l = len(requests)\n",
    "        res = []\n",
    "        # 选k个进行不重复组合\n",
    "        def dfs(temp, cur, k):\n",
    "            # 不够选了，剪枝\n",
    "            if len(temp) + l - cur < k:\n",
    "                return\n",
    "            # 满足条件，加入结果集\n",
    "            if len(temp) == k:\n",
    "                if test(temp) and temp not in res:\n",
    "                    res.append(temp[:])\n",
    "                    return\n",
    "                else:\n",
    "                    return\n",
    "            # 不选择当前请求\n",
    "            dfs(temp, cur + 1, k)\n",
    "            # 选择当前请求\n",
    "            dfs(temp + [requests[cur]], cur + 1, k)               \n",
    "        for i in range(0, l + 1):\n",
    "            dfs([], 0, i)\n",
    "        if len(res) == 0:\n",
    "            return 0\n",
    "        maxres = len(res[0])\n",
    "        for j in range(len(res)):\n",
    "            maxres = max(maxres, len(res[j]))\n",
    "        return maxres"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        m = len(requests)\n",
    "        for r in range(1, 1 << m):\n",
    "            cnt = [0] * n\n",
    "            tot = 0\n",
    "            rr = r\n",
    "            while rr:\n",
    "                lb = rr & -rr\n",
    "                cnt[requests[lb.bit_length() - 1][0]] -= 1\n",
    "                cnt[requests[lb.bit_length() - 1][1]] += 1\n",
    "                rr -= lb\n",
    "                tot += 1\n",
    "            if all(x == 0 for x in cnt):\n",
    "                ans = max(tot, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self,n, requests):\n",
    "        N = len(requests)\n",
    "        ans = []\n",
    "        tmp = [0 for i in range(N)]\n",
    "        def is_satisfy(tmp):\n",
    "            build_sit = [0 for i in range(n)] #所有大楼一开始都是空的\n",
    "            for i in range(N):\n",
    "                if tmp[i] == 1:\n",
    "                    leave = requests[i][0]\n",
    "                    reach = requests[i][1]\n",
    "                    build_sit[leave] -= 1\n",
    "                    build_sit[reach] += 1\n",
    "            if max(build_sit) - min(build_sit) == 0:\n",
    "                ans.append(sum(tmp))\n",
    "                \n",
    "        def calculate(i,tmp):\n",
    "            if i == N:\n",
    "                is_satisfy(tmp)\n",
    "            else:\n",
    "                tmp[i] = 0\n",
    "                calculate(i+1,tmp.copy())\n",
    "                tmp[i] = 1\n",
    "                calculate(i+1,tmp.copy())\n",
    "        calculate(0,tmp)\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = []\n",
    "        path = []\n",
    "        l = len(requests)\n",
    "        building = [0] * n\n",
    "\n",
    "        def valid():\n",
    "            for i in range(n):\n",
    "                if building[i] != 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == l:\n",
    "                if valid():\n",
    "                    ans.append(len(path))\n",
    "                return\n",
    "            \n",
    "            #不选\n",
    "            dfs(i+1)\n",
    "\n",
    "            #选\n",
    "            building[requests[i][0]] -= 1\n",
    "            building[requests[i][1]] += 1\n",
    "            path.append(i)\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "            building[requests[i][0]] += 1\n",
    "            building[requests[i][1]] -= 1\n",
    "        dfs(0)\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        m = len(requests)\n",
    "        ans = 0\n",
    "        for i in range(1,1<<m):\n",
    "            ct = 0\n",
    "            fg = [0]*n\n",
    "            f = True\n",
    "            for j in range(m):\n",
    "                if i&(1<<j):\n",
    "                    ct+=1\n",
    "                    fg[requests[j][1]]+=1\n",
    "                    fg[requests[j][0]]-=1\n",
    "            for c in fg:\n",
    "                if c:\n",
    "                    f = False\n",
    "                    break\n",
    "            if f:\n",
    "                ans = max(ans,ct)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        m = len(requests)\n",
    "        ans = 0\n",
    "        for i in range(1 << m):\n",
    "            diff = [0] * n\n",
    "            for j in range(m):\n",
    "                if i >> j & 1:\n",
    "                    a, b = requests[j]\n",
    "                    diff[a] -= 1\n",
    "                    diff[b] += 1\n",
    "            if all (x == 0 for x in diff):\n",
    "                ans = max(ans, i.bit_count())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        def is_valid(state):\n",
    "            net_changes = [0] * n\n",
    "            for i, (from_building, to_building) in enumerate(requests):\n",
    "                if ((state >> i) & 1) == 1:  # 检查请求是否被选择\n",
    "                    net_changes[from_building] -= 1\n",
    "                    net_changes[to_building] += 1\n",
    "            return all(change == 0 for change in net_changes)\n",
    "\n",
    "        max_requests = 0\n",
    "\n",
    "        for state in range(1 << len(requests)):  # 遍历所有可能的请求组合\n",
    "            if is_valid(state):\n",
    "                max_requests = max(max_requests, bin(state).count('1'))\n",
    "\n",
    "        return max_requests\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        B=[0]*n\n",
    "        m=len(requests)\n",
    "        maxCnt=0\n",
    "        cnt=0\n",
    "        def dfs(i):\n",
    "            nonlocal maxCnt, cnt\n",
    "            if i==m:\n",
    "                if all(b == 0 for b in B):\n",
    "                    maxCnt=max(maxCnt,cnt)\n",
    "                return\n",
    "            dfs(i+1)\n",
    "\n",
    "            cnt+=1\n",
    "            B[requests[i][0]]-=1\n",
    "            B[requests[i][1]]+=1\n",
    "            dfs(i+1)\n",
    "            cnt-=1\n",
    "            B[requests[i][0]]+=1\n",
    "            B[requests[i][1]]-=1\n",
    "        dfs(0)\n",
    "        return maxCnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        # 求最大环？\n",
    "        # 直接枚举所有的请求, 然后判断变化量是否为零\n",
    "        ans = 0\n",
    "        m = len(requests)\n",
    "        for r in range(1, 1 << m):\n",
    "            cnt = [0] * n\n",
    "            tot = 0\n",
    "            for i in range(r.bit_length()):\n",
    "                if r >> i & 1:\n",
    "                    cnt[requests[i][0]] -= 1\n",
    "                    cnt[requests[i][1]] += 1\n",
    "                    tot += 1\n",
    "            flag = True\n",
    "            for v in cnt:\n",
    "                if v != 0:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                ans = max(tot, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        m = len(requests)\n",
    "        ans = 0\n",
    "        for i in range(1,1<<m):\n",
    "            ct = i.bit_count()\n",
    "            if ct <= ans:\n",
    "                continue\n",
    "            fg = [0]*n\n",
    "            f = True\n",
    "            for j in range(m):\n",
    "                if i&(1<<j):\n",
    "                    fg[requests[j][1]]+=1\n",
    "                    fg[requests[j][0]]-=1\n",
    "            for c in fg:\n",
    "                if c:\n",
    "                    f = False\n",
    "                    break\n",
    "            if f:\n",
    "                ans = max(ans,ct)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1<<len(requests)):\n",
    "            cnt = i.bit_count()\n",
    "            if cnt <= ans:\n",
    "                continue\n",
    "            delta = [0] * n\n",
    "            for k,v in enumerate(requests):\n",
    "                if i & (1<<k):\n",
    "                    delta[v[0]] -= 1\n",
    "                    delta[v[1]] += 1\n",
    "            if all(y==0 for y in delta):\n",
    "                ans = cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        # 求最大环？\n",
    "        # 直接枚举所有的请求, 然后判断变化量是否为零\n",
    "        ans = 0\n",
    "        m = len(requests)\n",
    "        for r in range(1, 1 << m):\n",
    "            cnt = Counter()\n",
    "            tot = 0\n",
    "            for i in range(r.bit_length()):\n",
    "                if r >> i & 1:\n",
    "                    cnt[requests[i][0]] -= 1\n",
    "                    cnt[requests[i][1]] += 1\n",
    "                    tot += 1\n",
    "            flag = True\n",
    "            for k, v in cnt.items():\n",
    "                if v != 0:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                ans = max(tot, ans)\n",
    "        return ans\n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        for i in range(len(requests), 0, -1):\n",
    "            # 组合统计 m个requests里选取i个的所有组合\n",
    "            for comb in combinations(requests, i):\n",
    "                # 统计出度入度是否完全相等\n",
    "                cnts = [0] * n\n",
    "                for a, b in comb:\n",
    "                    # 出度, 入度\n",
    "                    cnts[a] += 1\n",
    "                    cnts[b] -= 1\n",
    "                if all(not c for c in cnts):\n",
    "                    return i\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        for k in range(len(requests), 0, -1):\n",
    "            for c in combinations(requests, k):\n",
    "                if Counter(a for a, b in c) == Counter(b for a, b in c):\n",
    "                    return k\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        m = len(requests)\n",
    "        ans = 0\n",
    "        count_from = [0] * n\n",
    "        count_to = [0] * n\n",
    "        pre = 0\n",
    "        def dfs(i):\n",
    "            if count_from == count_to:\n",
    "                nonlocal ans\n",
    "                ans = max(i, ans)\n",
    "\n",
    "            nonlocal pre\n",
    "            for j in range(pre,m):\n",
    "                count_from[requests[j][0]] += 1\n",
    "                count_to[requests[j][1]] += 1\n",
    "                pre = j + 1\n",
    "                dfs(i+1)\n",
    "\n",
    "                count_from[requests[j][0]] -= 1\n",
    "                count_to[requests[j][1]] -= 1\n",
    "        dfs(0)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        #dfs选或者不选，进行一次搜索，这里的搜索方法是深搜，因为这个写起来简便\n",
    "        change_lst=[0 for i in range(n)]\n",
    "        ans=-inf\n",
    "        count=0\n",
    "        #i划分楼栋序号,当前状态为i时刻的状态\n",
    "        def dfs(i,zeros):\n",
    "            nonlocal count\n",
    "            nonlocal ans\n",
    "            #捏妈的这里看了很久\n",
    "            if i==len(requests):\n",
    "                if zeros==n:\n",
    "                    ans=max(ans,count)\n",
    "                return\n",
    "            #choose,更新，这里有一个关键点，要考虑增加或者减少前为0，就-1，增加或者减少后为0，就+1\n",
    "            #z保存现场\n",
    "            z=zeros\n",
    "            a=requests[i][0]\n",
    "            b=requests[i][1]\n",
    "            count+=1\n",
    "            zeros-=change_lst[a]==0\n",
    "            change_lst[a]-=1\n",
    "            zeros+=change_lst[a]==0\n",
    "            zeros-=change_lst[b]==0\n",
    "            change_lst[b]+=1\n",
    "            zeros+=change_lst[b]==0\n",
    "            dfs(i+1,zeros)\n",
    "            #不选,不选要从前面的恢复现场\n",
    "            change_lst[a]+=1\n",
    "            change_lst[b]-=1\n",
    "            zeros=z\n",
    "            count-=1\n",
    "            dfs(i+1,zeros)\n",
    "        dfs(0,n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for mask in range(1 << len(requests)):\n",
    "            cnt = mask.bit_count()\n",
    "            if cnt <= ans:\n",
    "                continue\n",
    "            delta = [0] * n\n",
    "            for i, (x, y) in enumerate(requests):\n",
    "                if mask & (1 << i):\n",
    "                    delta[x] += 1\n",
    "                    delta[y] -= 1\n",
    "            if all(x == 0 for x in delta):\n",
    "                ans = cnt\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # delta=[0]*n\n",
    "        # m=len(requests)\n",
    "        # count,ret=0,0\n",
    "        # def dfs(i):\n",
    "        #     nonlocal count,ret\n",
    "        #     if i==m:\n",
    "        #         if all(x==0 for x in delta):\n",
    "        #             ret=max(ret,count)\n",
    "        #         return\n",
    "        #     dfs(i+1)\n",
    "        #     x,y=requests[i]\n",
    "        #     delta[x]-=1\n",
    "        #     delta[y]+=1\n",
    "        #     count+=1\n",
    "        #     dfs(i+1)\n",
    "        #     delta[x]+=1\n",
    "        #     delta[y]-=1\n",
    "        #     count-=1\n",
    "        # dfs(0)\n",
    "        # return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        def dfs(i, cnt):\n",
    "            nonlocal ans\n",
    "            if cnt + m1 - i <= ans:\n",
    "                return \n",
    "            if i == m1:\n",
    "                if all(x == 0 for x in delta) and cnt > ans:\n",
    "                    ans = cnt\n",
    "                return \n",
    "            x, y = requests[i]\n",
    "            delta[x] -= 1\n",
    "            delta[y] += 1\n",
    "            dfs(i + 1, cnt + 1)\n",
    "            delta[x] += 1\n",
    "            delta[y] -= 1\n",
    "            dfs(i + 1, cnt)\n",
    "\n",
    "        delta = [0] * n\n",
    "        ans = 0\n",
    "        m = len(requests) \n",
    "        requests = [[x,y] for x, y in requests if x != y]\n",
    "        m1 = len(requests)\n",
    "        dfs(0, 0) \n",
    "        return ans + m - m1 \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        lst=[0]*n\n",
    "        m=len(requests)\n",
    "        max_count=cur_count=0\n",
    "        def dfs(i):\n",
    "            nonlocal max_count,cur_count\n",
    "            if i==m:\n",
    "                if not any(lst) and cur_count>max_count:\n",
    "                    max_count=cur_count\n",
    "                return\n",
    "            x,y=requests[i]\n",
    "            lst[x]-=1\n",
    "            lst[y]+=1\n",
    "            cur_count+=1\n",
    "            dfs(i+1)\n",
    "            lst[x]+=1\n",
    "            lst[y]-=1\n",
    "            cur_count-=1\n",
    "            dfs(i+1)\n",
    "        dfs(0)\n",
    "        return max_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for mask in range(1 << len(requests)):\n",
    "            cnt = mask.bit_count()\n",
    "            if cnt <= ans:\n",
    "                continue\n",
    "            delta = [0] * n\n",
    "            for i, (x, y) in enumerate(requests):\n",
    "                if mask & (1 << i):\n",
    "                    delta[x] += 1\n",
    "                    delta[y] -= 1\n",
    "            if all(x == 0 for x in delta):\n",
    "                ans = cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        m = len(requests)\n",
    "        c = [0] * n\n",
    "        def dfs(i, p):\n",
    "            if i == m:\n",
    "                for x in c:\n",
    "                    if x != 0:\n",
    "                        return 0\n",
    "                return p\n",
    "            c[requests[i][0]] += 1\n",
    "            c[requests[i][1]] -= 1\n",
    "            pm = dfs(i + 1, p + 1)\n",
    "            c[requests[i][0]] -= 1\n",
    "            c[requests[i][1]] += 1\n",
    "            return max(pm, dfs(i + 1, p))\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        flag = [0] * n\n",
    "        ans = 0\n",
    "        def dfs(u, cnt):\n",
    "            nonlocal ans\n",
    "            if u == len(requests):\n",
    "                if flag == [0] * n:\n",
    "                    ans = max(ans, cnt)\n",
    "                return\n",
    "                \n",
    "            dfs(u + 1, cnt)\n",
    "            leave, to = requests[u]\n",
    "            flag[leave] -= 1\n",
    "            flag[to] += 1\n",
    "            dfs(u + 1, cnt + 1)\n",
    "            flag[leave] += 1\n",
    "            flag[to] -= 1\n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        delta = [0] * n\n",
    "        ans, cnt, zero = 0, 0, n\n",
    "\n",
    "        def dfs(pos: int) -> None:\n",
    "            nonlocal ans, cnt, zero\n",
    "            if pos == len(requests):\n",
    "                if zero == n:\n",
    "                    ans = max(ans, cnt)\n",
    "                return\n",
    "            \n",
    "            dfs(pos + 1)\n",
    "\n",
    "            z = zero\n",
    "            cnt += 1\n",
    "            x, y = requests[pos]\n",
    "            zero -= delta[x] == 0\n",
    "            delta[x] -= 1\n",
    "            zero += delta[x] == 0\n",
    "            zero -= delta[y] == 0\n",
    "            delta[y] += 1\n",
    "            zero += delta[y] == 0\n",
    "            dfs(pos + 1)\n",
    "            delta[y] -= 1\n",
    "            delta[x] += 1\n",
    "            cnt -= 1\n",
    "            zero = z\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        req = [0] * n\n",
    "\n",
    "        def check() -> bool:\n",
    "            for r in req:\n",
    "                if r != 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def dfs(idx: int, num: int):\n",
    "            if idx == len(requests):\n",
    "                if check():\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans, num)\n",
    "                return\n",
    "            dfs(idx + 1, num)\n",
    "            _from = requests[idx][0]\n",
    "            _to = requests[idx][1]\n",
    "            req[_from] -= 1\n",
    "            req[_to] += 1\n",
    "            dfs(idx + 1, num + 1)\n",
    "            req[_from] += 1\n",
    "            req[_to] -= 1\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        delta = [0] * n\n",
    "        ans = 0\n",
    "        def dfs(i, cnt):\n",
    "            nonlocal ans\n",
    "            if cnt + len(requests) - i <= ans:\n",
    "                return \n",
    "            if i == len(requests):\n",
    "                if all(x == 0 for x in delta):\n",
    "                    ans = max(cnt, ans)\n",
    "                return \n",
    "            x, y = requests[i]\n",
    "            delta[x] -= 1\n",
    "            delta[y] += 1\n",
    "            dfs(i + 1, cnt + 1)\n",
    "            delta[x] += 1\n",
    "            delta[y] -= 1\n",
    "            dfs(i + 1, cnt)\n",
    "        dfs(0, 0) \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        # 获取提交调动请求的员工数量\n",
    "        m = len(requests)\n",
    "        \n",
    "        # max_status 代表的是所有可能的处理方式，对于每个员工，我们都可以选择接受或不接受其调动请求，所以总共有 2^m 种可能的处理方式\n",
    "        max_status = 1 << m\n",
    "        \n",
    "        # 初始化最多接受的调动请求数量为 0\n",
    "        res = 0\n",
    "        \n",
    "        # 初始化每个部门的人员净变化为 0\n",
    "        net_change_arr = [0] * n\n",
    "\n",
    "        # 枚举所有可能的处理方式\n",
    "        for i in range(max_status):\n",
    "            # 初始化临时的人员净变化数组\n",
    "            tmp = [0] * n\n",
    "            # 当前处理方式对应的二进制数\n",
    "            state = i\n",
    "            # 初始化接受的调动请求数量为 0\n",
    "            cnt = 0\n",
    "            \n",
    "            # 遍历每个员工的调动请求\n",
    "            for idx in range(m):\n",
    "                # 如果当前处理方式中，该员工的调动请求被接受，那么在二进制数中，该位置应该是 1\n",
    "                is_accept = state & 1\n",
    "                if is_accept == 1:\n",
    "                    # 如果该员工的调动请求被接受，那么需要更新人员净变化数组\n",
    "                    from_, to = requests[idx]\n",
    "                    tmp[from_] -= 1\n",
    "                    tmp[to] += 1\n",
    "                    cnt += 1\n",
    "                # 更新二进制数，准备处理下一个员工的调动请求\n",
    "                state >>= 1\n",
    "            \n",
    "            # 如果这种处理方式满足每个部门的人员净变化为 0 的条件，那么更新最多接受的调动请求数量\n",
    "            if tmp == net_change_arr:\n",
    "                res = max(res, cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        window = [0]*n\n",
    "        num = len(requests)\n",
    "        res = 0\n",
    "        res1 = 0\n",
    "        def dfs(i):\n",
    "            nonlocal res1,res\n",
    "            if i == num:\n",
    "                if window == [0]*n:\n",
    "                    res =  max(res,res1)\n",
    "                return \n",
    "            \n",
    "            dfs(i+1)\n",
    "\n",
    "            x,y = requests[i]\n",
    "            res1 += 1\n",
    "            window[x] -= 1\n",
    "            window[y] += 1\n",
    "            dfs(i+1)\n",
    "            window[y] -= 1\n",
    "            window[x] += 1\n",
    "            res1 -= 1\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        # 获取提出更换请求的员工个数\n",
    "        m = len(requests)\n",
    "        # max_status 代表的是员工的状态 -----> 员工请求的请求可以被接受 / 不接受 每个员工有两种状态 那么就有 2^m 次种状态结果\n",
    "        max_status = 1 << m\n",
    "        res = 0\n",
    "        # 记录是否成功接受请求的数组\n",
    "        net_change_arr = [0] * n\n",
    "\n",
    "        # 枚举所有状态，二进制中 1 的个数为当前状态的请求个数\n",
    "        for i in range(max_status):\n",
    "            tmp = [0] * n\n",
    "            state = i\n",
    "            # 用于记录当前的员工请求下标\n",
    "            idx = 0\n",
    "            # 用于记录当前状态下的接受的请求个数\n",
    "            cnt = 0\n",
    "            # 用于获取当前状态中二进制数字中1的个数\n",
    "            while state > 0:\n",
    "                # 判断最后一位是否为1\n",
    "                is_accept = state & 1\n",
    "                # 如果为 1 则说明了当前状态被接受了 需要记录住房情况\n",
    "                if is_accept == 1:\n",
    "                    # 获取需要从哪里 搬到 哪里的位置信息\n",
    "                    from_, to = requests[idx]\n",
    "                    # 记录住房净变化\n",
    "                    tmp[from_] -= 1\n",
    "                    tmp[to] += 1\n",
    "                    cnt += 1\n",
    "                # 获取前一个员工的状态请求情况\n",
    "                state >>= 1\n",
    "                idx += 1\n",
    "            # 根据我们上面完成得到记录住房变化 需要满足每栋楼员工净变化为 0\n",
    "            # 滚动获取最大值\n",
    "            if tmp == net_change_arr:\n",
    "                res = max(res, cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        lst=[0]*n\n",
    "        m=len(requests)\n",
    "        max_count=cur_count=0\n",
    "        def dfs(i):\n",
    "            nonlocal max_count,cur_count\n",
    "            if i==m:\n",
    "                if not any(lst) and cur_count>max_count:\n",
    "                    max_count=cur_count\n",
    "                return\n",
    "            x,y=requests[i]\n",
    "            lst[x]-=1\n",
    "            lst[y]+=1\n",
    "            cur_count+=1\n",
    "            dfs(i+1)\n",
    "            lst[x]+=1\n",
    "            lst[y]-=1\n",
    "            cur_count-=1\n",
    "            dfs(i+1)\n",
    "        dfs(0)\n",
    "        return max_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        net = [0] * n\n",
    "        k = len(requests)\n",
    "        def dfs(i, cnt):\n",
    "            if cnt > 0 and set(net) == {0}:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, cnt)\n",
    "            if i == k:\n",
    "                return\n",
    "            dfs(i+1, cnt)\n",
    "            net[requests[i][0]] -= 1\n",
    "            net[requests[i][1]] += 1\n",
    "            dfs(i+1, cnt+1)\n",
    "            net[requests[i][0]] += 1\n",
    "            net[requests[i][1]] -= 1\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        def check(rs):\n",
    "            vs = [0] * n\n",
    "            for (f, t) in rs:\n",
    "                vs[f] += 1\n",
    "                vs[t] -= 1\n",
    "            return all(v == 0 for v in vs)\n",
    "\n",
    "        ans = [0]\n",
    "        a = []\n",
    "\n",
    "        def dfs(begin):\n",
    "            # print(a)\n",
    "            if check(a):\n",
    "                ans[0] = max(ans[0], len(a))\n",
    "\n",
    "            for i in range(begin, len(requests)):\n",
    "                a.append(requests[i])\n",
    "                dfs(i + 1)\n",
    "                a.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        print(ans)\n",
    "        return ans[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        m = len(requests)\n",
    "        for r in range(1, 1 << m):\n",
    "            cnt = [0] * n\n",
    "            tot = 0\n",
    "            rr = r\n",
    "            while rr:\n",
    "                lb = rr & -rr\n",
    "                cnt[requests[lb.bit_length() - 1][0]] -= 1\n",
    "                cnt[requests[lb.bit_length() - 1][1]] += 1\n",
    "                rr -= lb\n",
    "                tot += 1\n",
    "            if all(x == 0 for x in cnt):\n",
    "                ans = max(tot, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        diff = [0] * n\n",
    "        def dfs(i: int, cnt: int) -> None:\n",
    "            if i == len(requests):\n",
    "                for x in diff:\n",
    "                    if x != 0:\n",
    "                        return\n",
    "                nonlocal ans\n",
    "                ans = max(ans, cnt)\n",
    "                return\n",
    "            dfs(i + 1, cnt)\n",
    "            [f, t] = requests[i]\n",
    "            diff[f] -= 1\n",
    "            diff[t] += 1\n",
    "            dfs(i + 1, cnt + 1)\n",
    "            diff[f] += 1\n",
    "            diff[t] -= 1\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        m=len(requests)\n",
    "        res=0\n",
    "        path=[]\n",
    "        def dfs(i):\n",
    "            nonlocal res\n",
    "            if i==m:\n",
    "                cnt1=[0]*n\n",
    "                cnt2=[0]*n\n",
    "                final_path=path.copy()\n",
    "                for item in final_path:\n",
    "                    cnt1[item[0]] +=1\n",
    "                    cnt2[item[1]] +=1\n",
    "                if cnt1==cnt2:\n",
    "                    res = max(res,len(final_path))\n",
    "                return \n",
    "\n",
    "            dfs(i+1)\n",
    "\n",
    "            path.append(requests[i])\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "        dfs(0)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        z = [0] * n\n",
    "        nt = len(requests)\n",
    "        def dfs(i,ct):\n",
    "            if i == nt:\n",
    "                if set(z) == {0}:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans, ct)\n",
    "                return\n",
    "            dfs(i+1,ct)\n",
    "\n",
    "            z[requests[i][0]] -= 1\n",
    "            z[requests[i][1]] += 1\n",
    "            dfs(i+1,ct+1)\n",
    "            z[requests[i][1]] -= 1\n",
    "            z[requests[i][0]] += 1\n",
    "        dfs(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        m = 1 << len(requests) \n",
    "        ans = 0\n",
    "        \n",
    "        def getCnt(num:int) -> int:\n",
    "            res = 0 \n",
    "            while num:\n",
    "                if num&1:\n",
    "                    res +=1 \n",
    "                num >>=1\n",
    "            return res \n",
    "        def check(num:int) -> bool:\n",
    "            cnt = [0]*20\n",
    "            sum = 0\n",
    "            idx = 0\n",
    "            while num:\n",
    "                if num&1:\n",
    "                    a = requests[idx][0]\n",
    "                    b = requests[idx][1]\n",
    "                    cnt[a]+=1\n",
    "                    if cnt[a] ==1:\n",
    "                        sum +=1\n",
    "                    cnt[b]-=1\n",
    "                    if cnt[b] == 0:\n",
    "                        sum -=1\n",
    "                num >>= 1\n",
    "                idx +=1\n",
    "            return sum == 0\n",
    "                    \n",
    "                \n",
    "        for i in range(1,m):\n",
    "            cnt = getCnt(i)\n",
    "            if cnt <= ans :\n",
    "                continue\n",
    "            if check(i):\n",
    "                ans = cnt \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        # m = len(requests)\n",
    "        # ans = 0\n",
    "        # for i in range(1 << m):\n",
    "        #     diff = [0] * n\n",
    "        #     for j in range(m):\n",
    "        #         if i >> j & 1:\n",
    "        #             a, b = requests[j]\n",
    "        #             diff[a] -= 1\n",
    "        #             diff[b] += 1\n",
    "        #     if all (x == 0 for x in diff):\n",
    "        #         ans = max(ans, i.bit_count())\n",
    "        # return ans\n",
    "        m = len(requests)\n",
    "        ans = 0\n",
    "        diff = [0] * n\n",
    "        def dfs(i, cnt):\n",
    "            nonlocal ans\n",
    "            if i == m:\n",
    "                if all (x == 0 for x in diff):\n",
    "                    ans = max(ans, cnt)\n",
    "                return\n",
    "            dfs(i + 1, cnt)\n",
    "            a, b = requests[i]\n",
    "            diff[a] -= 1\n",
    "            diff[b] += 1\n",
    "            dfs(i + 1, cnt + 1)\n",
    "            diff[a] += 1\n",
    "            diff[b] -= 1\n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        buildings = [0] * n\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(i, t):\n",
    "            nonlocal ans\n",
    "            if i == len(requests):\n",
    "                if all(x == 0 for x in buildings):\n",
    "                    ans = max(ans, t)\n",
    "                return \n",
    "\n",
    "            # choose\n",
    "            buildings[requests[i][0]] -= 1\n",
    "            buildings[requests[i][1]] += 1\n",
    "            dfs(i+1, t+1)\n",
    "            buildings[requests[i][0]] += 1\n",
    "            buildings[requests[i][1]] -= 1\n",
    "            # not choose\n",
    "            dfs(i+1, t)\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = -1\n",
    "        m = len(requests)\n",
    "        def count_bit(bit) -> int:\n",
    "            x = bit\n",
    "            cnt = 0\n",
    "            while x:\n",
    "                cnt += 1\n",
    "                x &= (x - 1)\n",
    "            return cnt\n",
    "        for bit in range(1 << m):\n",
    "            deg = [0] * n\n",
    "            for j in range(m):\n",
    "                if bit >> j & 1:\n",
    "                    deg[requests[j][0]] -= 1\n",
    "                    deg[requests[j][1]] += 1\n",
    "            if deg == [0] * n:\n",
    "                ans = max(ans,bit.bit_count())\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = -1\n",
    "        m = len(requests)\n",
    "        def count_bit(bit) -> int:\n",
    "            x = bit\n",
    "            cnt = 0\n",
    "            while x:\n",
    "                cnt += 1\n",
    "                x &= (x - 1)\n",
    "            return cnt\n",
    "        for bit in range(1 << m):\n",
    "            deg = [0] * n\n",
    "            for j in range(m):\n",
    "                if bit >> j & 1:\n",
    "                    deg[requests[j][0]] -= 1\n",
    "                    deg[requests[j][1]] += 1\n",
    "            if deg == [0] * n:\n",
    "                ans = max(ans,count_bit(bit))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        for i in range(len(requests), 0, -1):\n",
    "            # 组合统计 m个requests里选取i个的所有组合\n",
    "            for comb in combinations(requests, i):\n",
    "                # 统计出度入度是否完全相等\n",
    "                cnts = [0] * n\n",
    "                for a, b in comb:\n",
    "                    # 出度, 入度\n",
    "                    cnts[a] += 1\n",
    "                    cnts[b] -= 1\n",
    "                if all(not c for c in cnts):\n",
    "                    return i\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        count = 0\n",
    "        nums = [0] * n\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal res, count, nums\n",
    "            if check(nums):\n",
    "                res = max(res, count)\n",
    "\n",
    "            for j in range(i, len(requests)):\n",
    "                count += 1\n",
    "                nums[requests[j][0]] -= 1\n",
    "                nums[requests[j][1]] += 1\n",
    "                dfs(j+1)\n",
    "                nums[requests[j][1]] -= 1\n",
    "                nums[requests[j][0]] += 1\n",
    "                count -= 1\n",
    "        \n",
    "        def check(nums):\n",
    "            for x in nums:\n",
    "                if x != 0: return False\n",
    "            return True\n",
    "        \n",
    "        dfs(0)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = -1\n",
    "        m = len(requests)\n",
    "        for bit in range(1 << m):\n",
    "            deg = [0] * n\n",
    "            for j,(x,y) in enumerate(requests):\n",
    "                if bit >> j & 1:\n",
    "                    deg[x] -= 1\n",
    "                    deg[y] += 1\n",
    "            if deg == [0] * n:\n",
    "                ans = max(ans,bit.bit_count())\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        a = [0] * n\n",
    "        l = len(requests)\n",
    "        ret = [0]\n",
    "\n",
    "        def dfs(i, bb,deep):\n",
    "            if bb == 0 and ret[0] < deep:\n",
    "                    ret[0] = deep\n",
    "            if i >= l:\n",
    "                return\n",
    "            for j in range(i, l):\n",
    "                a[requests[j][0]] -= 1\n",
    "                t = (1 << requests[j][0])\n",
    "                tmbb = bb\n",
    "                if a[requests[j][0]] == 0 and (bb & t) > 0:\n",
    "                    bb -= t\n",
    "                if a[requests[j][0]] != 0 and (bb & t) == 0:\n",
    "                    bb += t\n",
    "                a[requests[j][1]] += 1\n",
    "                t = (1 << requests[j][1])\n",
    "                if a[requests[j][1]] == 0 and (bb & t) > 0:\n",
    "                    bb -= t\n",
    "                if a[requests[j][1]] != 0 and (bb & t) == 0:\n",
    "                    bb += t\n",
    "                dfs(j + 1, bb, deep+1)\n",
    "                bb = tmbb\n",
    "                a[requests[j][0]] += 1\n",
    "                a[requests[j][1]] -= 1\n",
    "        dfs(0, 0, 0)\n",
    "        return ret[0]\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        m = len(requests)\n",
    "        d = defaultdict(int)\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == m:\n",
    "                for i in range(n):\n",
    "                    if d[i] != 0:\n",
    "                        return -inf\n",
    "                return 0\n",
    "            # 选\n",
    "            f,t = requests[i]\n",
    "            d[f] -= 1\n",
    "            d[t] += 1\n",
    "            ans = dfs(i + 1) + 1\n",
    "            d[f] += 1\n",
    "            d[t] -= 1\n",
    "            ans = max(ans,dfs(i + 1))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        delta = [0] * n\n",
    "        ans = 0\n",
    "        def dfs(i, cnt):\n",
    "            nonlocal ans\n",
    "            if cnt + len(requests) - i <= ans:\n",
    "                return \n",
    "            if i == len(requests):\n",
    "                if all(x == 0 for x in delta):\n",
    "                    ans = max(cnt, ans)\n",
    "                return \n",
    "            x, y = requests[i]\n",
    "            delta[x] -= 1\n",
    "            delta[y] += 1\n",
    "            dfs(i + 1, cnt + 1)\n",
    "            delta[x] += 1\n",
    "            delta[y] -= 1\n",
    "            dfs(i + 1, cnt)\n",
    "\n",
    "        m = len(requests) \n",
    "        requests = [[x,y] for x, y in requests if x != y]\n",
    "        dfs(0, 0) \n",
    "        return ans + m - len(requests)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ls=[0]*n\n",
    "        ans=0\n",
    "        m=len(requests)\n",
    "        def dfs(x,r):\n",
    "            nonlocal ans\n",
    "            #if m-x-1+r<ans:\n",
    "            #    return \n",
    "            if x==m:\n",
    "                valid=True\n",
    "                for i in range(n):\n",
    "                    if ls[i]!=0:\n",
    "                        valid=False\n",
    "                        break\n",
    "                if valid:\n",
    "                    ans=max(ans,r)\n",
    "                return \n",
    "            a,b=requests[x]\n",
    "            ls[a]+=1\n",
    "            ls[b]-=1\n",
    "            dfs(x+1,r+1)\n",
    "            ls[a]-=1\n",
    "            ls[b]+=1\n",
    "            dfs(x+1,r)\n",
    "        dfs(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        # m = len(requests)\n",
    "        # ans = 0\n",
    "        # path = []\n",
    "        # def dfs(i):\n",
    "        #     nonlocal ans\n",
    "        #     if i == m:\n",
    "        #         count_from = [0] * n\n",
    "        #         count_to = [0] * n\n",
    "        #         for item in path.copy():\n",
    "        #             count_from[item[0]] += 1\n",
    "        #             count_to[item[1]]  += 1\n",
    "        #         if count_from == count_to:\n",
    "        #             ans = max(ans,len(path.copy()))\n",
    "        #         return\n",
    "        #     dfs(i+1)\n",
    "        #     path.append(requests[i])\n",
    "        #     dfs(i+1)\n",
    "        #     path.pop()\n",
    "        # dfs(0)\n",
    "        # return ans\n",
    "        m = len(requests)\n",
    "        ans = 0\n",
    "        path = []\n",
    "        def dfs(i):\n",
    "            if i == m + 1:\n",
    "                return\n",
    "            nonlocal ans\n",
    "            count_from = [0] * n \n",
    "            count_to = [0] * n\n",
    "            final_path = path[:]\n",
    "            for item in path.copy():\n",
    "                count_from[item[0]] += 1\n",
    "                count_to[item[1]] += 1\n",
    "            if count_from == count_to:\n",
    "                ans = max(ans,len(path.copy()))\n",
    "            for j in range(i,m):\n",
    "                path.append(requests[j])\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        m = len(requests)\n",
    "        for i in range(1, 1 << m):\n",
    "            degree = [0] * n\n",
    "            cnt = 0\n",
    "            for j in range(m):\n",
    "                if i & (1 << j):\n",
    "                    cnt += 1\n",
    "                    a, b = requests[j]\n",
    "                    degree[a] -= 1\n",
    "                    degree[b] += 1\n",
    "            if all(not d for d in degree):\n",
    "                ans = ans if ans > cnt else cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        path = [0]*n\n",
    "        allow = []\n",
    "        n_r = len(requests)\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if path == [0]*n:\n",
    "                ans = max(ans, len(allow))\n",
    "\n",
    "            if i == n_r:\n",
    "                return\n",
    "            \n",
    "            for j in range(i, n_r):\n",
    "                path[requests[j][0]] -= 1\n",
    "                path[requests[j][1]] += 1\n",
    "                allow.append(requests[j])\n",
    "                dfs(j+1)\n",
    "                path[requests[j][0]] += 1\n",
    "                path[requests[j][1]] -= 1\n",
    "                allow.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "\n",
    "        m = len(requests)\n",
    "        buildings = [0] * n\n",
    "        ans = 0\n",
    "        fulfilled = 0\n",
    "\n",
    "        def avaliable():\n",
    "            for building in buildings:\n",
    "                if building != 0: return False\n",
    "            return True\n",
    "\n",
    "        def backtrace(i):\n",
    "            nonlocal ans\n",
    "            nonlocal fulfilled\n",
    "            if i == m:\n",
    "                if avaliable():\n",
    "                    ans = max(ans,fulfilled)\n",
    "                return\n",
    "            \n",
    "            #skip\n",
    "            backtrace(i+1)\n",
    "\n",
    "            #pick\n",
    "            moveout = requests[i][0]\n",
    "            movein = requests[i][1]\n",
    "            buildings[moveout] -= 1\n",
    "            buildings[movein] += 1\n",
    "            fulfilled += 1\n",
    "            backtrace(i+1)\n",
    "            buildings[moveout] += 1\n",
    "            buildings[movein] -= 1\n",
    "            fulfilled -= 1\n",
    "        backtrace(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    #     def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\r\n",
    "    #         l = len(requests)\r\n",
    "    #         path = 0\r\n",
    "    #         nums = [0] * n\r\n",
    "    #         res = 0\r\n",
    "\r\n",
    "    #         def dfs(i):\r\n",
    "    #             nonlocal path\r\n",
    "    #             if i == l:\r\n",
    "    #                 nonlocal res\r\n",
    "    #                 if all(num == 0 for num in nums):\r\n",
    "    #                     res = max(res, path)\r\n",
    "    #                 return\r\n",
    "    #             dfs(i + 1)\r\n",
    "\r\n",
    "    #             nums[requests[i][0]] -= 1\r\n",
    "    #             nums[requests[i][1]] += 1\r\n",
    "    #             path += 1\r\n",
    "    #             dfs(i + 1)\r\n",
    "    #             nums[requests[i][0]] += 1\r\n",
    "    #             nums[requests[i][1]] -= 1\r\n",
    "    #             path -= 1\r\n",
    "\r\n",
    "    #         dfs(0)\r\n",
    "    #         return res\r\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\r\n",
    "        l = len(requests)\r\n",
    "        res = 0\r\n",
    "        nums = [0] * n\r\n",
    "\r\n",
    "        def dfs(i, d):\r\n",
    "            if all(x == 0 for x in nums):\r\n",
    "                nonlocal res\r\n",
    "                res = max(res, d)\r\n",
    "            if i == l:\r\n",
    "                return\r\n",
    "            for j in range(i, l):\r\n",
    "                nums[requests[j][0]] -= 1\r\n",
    "                nums[requests[j][1]] += 1\r\n",
    "\r\n",
    "                dfs(j + 1, d + 1)\r\n",
    "\r\n",
    "                nums[requests[j][0]] += 1\r\n",
    "                nums[requests[j][1]] -= 1\r\n",
    "\r\n",
    "        dfs(0, 0)\r\n",
    "        return res\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        delta=[0]*n\n",
    "        m=len(requests)\n",
    "        count,ret=0,0\n",
    "        def dfs(i):\n",
    "            nonlocal count,ret\n",
    "            if i==m:\n",
    "                if all(map(lambda x:x==0,delta)):\n",
    "                    ret=max(ret,count)\n",
    "                return\n",
    "            dfs(i+1)\n",
    "            x,y=requests[i]\n",
    "            delta[x]-=1\n",
    "            delta[y]+=1\n",
    "            count+=1\n",
    "            dfs(i+1)\n",
    "            delta[x]+=1\n",
    "            delta[y]-=1\n",
    "            count-=1\n",
    "        dfs(0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        delta=[0]*n\n",
    "        m=len(requests)\n",
    "        count,ret=0,0\n",
    "        def dfs(i):\n",
    "            nonlocal count,ret\n",
    "            if i==m:\n",
    "                if all(x==0 for x in delta):\n",
    "                    ret=max(ret,count)\n",
    "                return\n",
    "            dfs(i+1)\n",
    "            x,y=requests[i]\n",
    "            delta[x]-=1\n",
    "            delta[y]+=1\n",
    "            count+=1\n",
    "            dfs(i+1)\n",
    "            delta[x]+=1\n",
    "            delta[y]-=1\n",
    "            count-=1\n",
    "        dfs(0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        cnt=[0]*n\n",
    "        m=len(requests)\n",
    "        def dfs(i,picked):\n",
    "            nonlocal cnt\n",
    "            if i==m:\n",
    "                for c in cnt:\n",
    "                    if c!=0:\n",
    "                        return 0\n",
    "                return picked\n",
    "            cnt[requests[i][0]]+=1\n",
    "            cnt[requests[i][1]]-=1\n",
    "            pickMax=dfs(i+1, picked+1)\n",
    "            cnt[requests[i][0]]-=1\n",
    "            cnt[requests[i][1]]+=1\n",
    "\n",
    "            nopickMax=dfs(i+1, picked)\n",
    "            return max(pickMax,nopickMax)\n",
    "        return dfs(0, 0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        change = [0] * n\n",
    "        m = len(requests)\n",
    "        path = []\n",
    "        # 对于每个request都可以选or不选\n",
    "        # 选了就将cnt += 1，到最后看这个cnt对应的change做不做数，做数的话更新ans，不做数的话忽略\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if i == m:\n",
    "                change = [0] * n\n",
    "                for req in path:\n",
    "                    change[req[0]] -= 1\n",
    "                    change[req[1]] += 1\n",
    "                cnt = 0\n",
    "                if all(x == 0 for x in change):\n",
    "                    cnt = len(path)\n",
    "                ans = max(ans, cnt)\n",
    "                return\n",
    "\n",
    "            dfs(i + 1)\n",
    "\n",
    "            path.append(requests[i])\n",
    "            dfs(i + 1)\n",
    "            path.pop()\n",
    "            return \n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        count = [0] * n\n",
    "\n",
    "        def check():\n",
    "            for v in count:\n",
    "                if v != 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def dfs(i, move):\n",
    "            nonlocal res\n",
    "            if check():\n",
    "                res = max(res, move)\n",
    "            \n",
    "            for j in range(i, len(requests)):\n",
    "                count[requests[j][0]] -= 1\n",
    "                count[requests[j][1]] += 1\n",
    "                dfs(j + 1, move + 1)\n",
    "                count[requests[j][0]] += 1\n",
    "                count[requests[j][1]] -= 1\n",
    "        \n",
    "        dfs(0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        m = len(requests)\n",
    "        ans = 0\n",
    "        path= []\n",
    "        res = [0]*n # i楼正数表示进来，负数表示出去\n",
    "        # 选或者不选是更合适的\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if i == m:\n",
    "                if all(j == 0 for j in res):\n",
    "                    ans = max(ans,len(path))\n",
    "                return\n",
    "            # 不选\n",
    "            dfs(i+1)\n",
    "\n",
    "            # 选\n",
    "            res[requests[i][0]] -= 1\n",
    "            res[requests[i][1]] += 1\n",
    "            path.append(requests[i])\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "            res[requests[i][0]] += 1 # 粗心大意 之前现场没恢复完\n",
    "            res[requests[i][1]] -= 1 #\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        st = [0] * n\n",
    "        cnt = 0\n",
    "        zero = n\n",
    "        def process(idx):\n",
    "            nonlocal res, st, cnt, zero\n",
    "            if idx == len(requests):\n",
    "                if zero == n:\n",
    "                    res = max(res, cnt)\n",
    "                return\n",
    "            process(idx+1)\n",
    "            z = zero\n",
    "            cnt += 1\n",
    "            x, y = requests[idx]\n",
    "            if st[x] == 0:\n",
    "                zero -= 1\n",
    "            elif st[x] == 1:\n",
    "                zero += 1\n",
    "            st[x] -= 1\n",
    "            if st[y] == 0:\n",
    "                zero -= 1\n",
    "            elif st[y] == -1:\n",
    "                zero += 1\n",
    "            st[y] += 1\n",
    "            process(idx+1)\n",
    "            st[x] += 1\n",
    "            st[y] -= 1\n",
    "            cnt -= 1\n",
    "            zero = z\n",
    "        process(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ans = 0\n",
    "\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        builds = [[0, 0] for _ in range(n)]\n",
    "\n",
    "        def dfs(i, res_num):\n",
    "            if i == len(requests):\n",
    "                for a in builds:\n",
    "                    if a[0] != a[1]:\n",
    "                        return\n",
    "                if self.ans < res_num:\n",
    "                    self.ans = res_num\n",
    "            else:\n",
    "                dfs(i + 1, res_num)\n",
    "\n",
    "                f = requests[i][0]\n",
    "                t = requests[i][1]\n",
    "                builds[f][0] += 1\n",
    "                builds[t][1] += 1\n",
    "                dfs(i + 1, res_num + 1)\n",
    "                builds[f][0] -= 1\n",
    "                builds[t][1] -= 1\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\r\n",
    "        l = len(requests)\r\n",
    "        path = 0\r\n",
    "        nums = [0] * n\r\n",
    "        res = 0\r\n",
    "\r\n",
    "        def dfs(i):\r\n",
    "            nonlocal path\r\n",
    "            if i == l:\r\n",
    "                nonlocal res\r\n",
    "                if all(num == 0 for num in nums):\r\n",
    "                    res = max(res, path)\r\n",
    "                return\r\n",
    "            dfs(i + 1)\r\n",
    "\r\n",
    "            nums[requests[i][0]] -= 1\r\n",
    "            nums[requests[i][1]] += 1\r\n",
    "            path += 1\r\n",
    "            dfs(i + 1)\r\n",
    "            nums[requests[i][0]] += 1\r\n",
    "            nums[requests[i][1]] -= 1\r\n",
    "            path -= 1\r\n",
    "\r\n",
    "        dfs(0)\r\n",
    "        return res\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        m = len(requests)\n",
    "        path = []\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal m, n, ans \n",
    "\n",
    "            if i == m:\n",
    "                count1 = [0] * n\n",
    "                count2 = [0] * n\n",
    "                flag = path[:]\n",
    "                for p in flag:\n",
    "                    count1[p[0]] += 1\n",
    "                    count2[p[1]] += 1\n",
    "                if count1 == count2:\n",
    "                    ans = max(ans, len(flag))\n",
    "                    \n",
    "                return \n",
    "\n",
    "            dfs(i+1)\n",
    "\n",
    "            path.append(requests[i])\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        building = [0 for i in range(n)]\n",
    "        path = []\n",
    "        l = len(requests)\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if i == l:\n",
    "                if all(j == 0 for j in building):\n",
    "                    ans = max(ans,len(path))\n",
    "                return\n",
    "            dfs(i+1)\n",
    "            \n",
    "            path.append(i)\n",
    "            fro, to = requests[i]\n",
    "            building[fro] -= 1\n",
    "            building[to] += 1\n",
    "            dfs(i+1)\n",
    "            \n",
    "            path.pop()\n",
    "            building[fro] += 1\n",
    "            building[to] -= 1\n",
    "        dfs(0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        arr = [0] * n\n",
    "        req = []\n",
    "        rn = len(requests)\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            nonlocal arr\n",
    "            if i == rn:\n",
    "                # 核算\n",
    "                for r in req:\n",
    "                    arr[r[0]] -= 1\n",
    "                    arr[r[1]] += 1\n",
    "\n",
    "                for a in arr:\n",
    "                    if a != 0:\n",
    "                        arr = [0] * n\n",
    "                        return\n",
    "\n",
    "                ans = max(ans, len(req))\n",
    "                arr = [0] * n\n",
    "                return\n",
    "\n",
    "            dfs(i+1)\n",
    "            req.append(requests[i])\n",
    "            dfs(i+1)\n",
    "\n",
    "            req.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        path = []\n",
    "        m = len(requests)\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if i == m:\n",
    "                ch = path.copy()\n",
    "                tmp = [0]*n\n",
    "                for i in ch:\n",
    "                    a,b = requests[i][0],requests[i][1]\n",
    "                    tmp[a]-=1\n",
    "                    tmp[b]+=1\n",
    "                if not any(tmp):\n",
    "                    ans = max(ans,len(ch))\n",
    "                \"\"\"flg = False\n",
    "                for i in tmp:\n",
    "                    if i!=0:\n",
    "                        flg = True\n",
    "                        break\n",
    "                if not flg:\n",
    "                    \"\"\"\n",
    "                return\n",
    "            \n",
    "            dfs(i+1)\n",
    "            path.append(i)\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        # 1. 选/不选\n",
    "        m = len(requests)   # 需要满足的客户数量\n",
    "        path = []   # 存放当前枚举了哪些客户\n",
    "        res = 0\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal res\n",
    "            if i == m:    # 所有的客户都枚举完成\n",
    "                count1 = [0] * n   \n",
    "                count2 = [0] * n \n",
    "                final_path = path[:]\n",
    "                for item in final_path:   # 计算路径中的客户，所有客户是否满足：离开的楼号数量 == 搬进的楼号数量\n",
    "                    count1[item[0]] += 1\n",
    "                    count2[item[1]] += 1\n",
    "                if count1 == count2:\n",
    "                    res = max(res, len(final_path))   # res取最长的，符合要求的path\n",
    "                return\n",
    "            \n",
    "            dfs(i + 1)  # 不选第i个客户\n",
    "\n",
    "            path.append(requests[i])   # 选择满足第i个客户\n",
    "            dfs(i + 1)\n",
    "            path.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return res\n",
    "        \"\"\"\n",
    "        # 2. 枚举答案\n",
    "        # 思路：从j在[i, m]的范围内继续选择子集\n",
    "        m = len(requests)\n",
    "        path = []\n",
    "        res = 0\n",
    "        def dfs(i):\n",
    "\n",
    "            nonlocal res\n",
    "            \n",
    "            count1 = [0] * n   \n",
    "            count2 = [0] * n \n",
    "            final_path = path[:]\n",
    "            for item in final_path:   # 计算路径中的客户，所有客户是否满足：离开的楼号数量 == 搬进的楼号数量\n",
    "                count1[item[0]] += 1\n",
    "                count2[item[1]] += 1\n",
    "            if count1 == count2:\n",
    "                res = max(res, len(final_path))   # res取最长的，符合要求的path\n",
    "            if i == m:\n",
    "                return\n",
    "            \n",
    "            for j in range(i, m):\n",
    "                path.append(requests[j])\n",
    "                dfs(j + 1)\n",
    "                path.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        m = len(requests) # 注意区分一下m和n\n",
    "        ans = 0\n",
    "        path= []\n",
    "        res = [0]*n # i楼正数表示进来，负数表示出去\n",
    "        # 选或者不选是更合适的\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if i == m:\n",
    "                if all(j == 0 for j in res):\n",
    "                    ans = max(ans,len(path))\n",
    "                return\n",
    "            # 不选\n",
    "            dfs(i+1)\n",
    "\n",
    "            # 选\n",
    "            res[requests[i][0]] -= 1\n",
    "            res[requests[i][1]] += 1\n",
    "            path.append(requests[i])\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "            res[requests[i][0]] += 1 # 粗心大意 之前现场没恢复完\n",
    "            res[requests[i][1]] -= 1 #\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n",
    "        m = len(requests)\n",
    "        # 存放当前枚举了哪些客户\n",
    "        path = []\n",
    "        res = 0\n",
    "        def dfs(i):\n",
    "            nonlocal res\n",
    "            if i == m:\n",
    "                count1 = [0] * n\n",
    "                count2 = [0] * n\n",
    "                final_path = path.copy()\n",
    "                for item in final_path:\n",
    "                    count1[item[0]] += 1\n",
    "                    count2[item[1]] += 1\n",
    "                if count1 == count2:\n",
    "                    res = max(res, len(final_path))\n",
    "                return\n",
    "            dfs(i+1)\n",
    "\n",
    "            path.append(requests[i])\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "        dfs(0)\n",
    "        return res\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
